home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / The World of Computer Software.iso / superopt.zip / README < prev    next >
Text File  |  1992-11-28  |  5KB  |  152 lines
  1.  
  2.             GNU SUPEROPTIMIZER
  3.  
  4. The superoptimizer is a function sequence generator that uses a exhaustive
  5. generate-and-test approach to find the shortest instruction sequence for a
  6. given function.  You have to tell the superoptimizer which function and
  7. which CPU you want to get code for, and how many instructions you can
  8. accept.
  9.  
  10. The superoptimizer can't generate very long sequences, unless you have a
  11. very fast computer or very much spare time.  The time complexity of the
  12. used algorithm is approximately
  13.  
  14.          2 n
  15.     O(m n )
  16.  
  17. where m is the number of available instructions on the architecture and n
  18. is the shortest sequence for the goal function.
  19.  
  20. The superoptimizer can't guarantee that it finds the best possible
  21. instruction sequences for all possible functions.  For example, it doesn't
  22. even try to include immediate constants (other that -1, 0, +1, and the
  23. smallest negative and biggest positive numbers) in the sequences.  It often
  24. makes a good job for functions that depend on registers only.
  25.  
  26. WARNING!  The generated sequences might be incorrect with a very small
  27. probability.  Always make sure a sequence is correct before using it.  So
  28. far, I have never discovered any incorrect sequences.  If you find one,
  29. please let me know about it!
  30.  
  31.  
  32.             USAGE INSTRUCTIONS
  33.  
  34. The superoptimizer supports 7 CPUs, SPARC, Motorola 68000 and 88000, IBM
  35. RS/6000, AMD 29000, Intel 80x86, and Pyramid.
  36.  
  37. You need an ANSI C compiler, for example GCC, to compile the
  38. superoptimizer.  Type
  39.  
  40.     make CPU=-D<cpuname> gso
  41.  
  42. or simply
  43.  
  44.     gcc -O -g -D<cpuname> superopt.c -o gso
  45.  
  46. where <cpuname> is one of SPARC, M68000, M88000, RS6000, AM29K, I386, or
  47. PYR.  To run the superoptimizer, type
  48.  
  49.     gso -f<goal-function> [-assembler] [-max-cost n] [-no-carry-insns]
  50.        [-extra-cost n]
  51.  
  52. and wait until the found instructions sequences are printed.
  53.  
  54.  
  55.             OPTIONS
  56.  
  57. The `-f' option has always to be defined to tell the superoptimizer for
  58. which function it should try to to find an instruction sequence.  See below
  59. for possible function names.
  60.  
  61. Option names may be abbreviated.
  62.  
  63. -assembler
  64.     Output assembler suitable to feed /bin/as instead of pseudo-code
  65.     suitable for humans.
  66.  
  67. -max-cost n
  68.     Limit the `cost' of the instruction sequence to n.  May be used to
  69.     stop the search if no instruction sequence of that length or
  70.     shorter is found.  By default this is 5.
  71.  
  72. -extra-cost n
  73.     Search for sequences n more expensive than the cheapest found
  74.     sequence.  Default is 0 meaning that only the cheapest sequence(s)
  75.     are printed.
  76.  
  77. -no-carry-insns
  78.     Don't use instructions that use the carry flag.  This might be
  79.     desirable on RISCs to simplify instruction scheduling.
  80.  
  81. -f<goal-function-name>
  82.     
  83.     where <goal-function-name> is one of eq, ne, les, ges, lts, gts,
  84.     leu, geu, ltu, gtu, eq0, ne0, les0, ges0, lts0, gts0, neq, nne,
  85.     nles, nges, nlts, ngts, nleu, ngeu, nltu, ngtu, neq0, nne0, nles0,
  86.     nges0, nlts0, ngts0, maxs, mins, maxu, minu, sgn, abs, nabs, gray,
  87.     or gray2, etc, etc.
  88.  
  89.     eq, ne, les, etc, computes the C expression "a == b", "a != b", "a
  90.     <= b", etc, where the operation codes ending in `s' indicates
  91.     signed comparison; `u` indicates unsigned comparison.
  92.  
  93.     eq0,... computes "a == 0", ...
  94.  
  95.     The `n' before the names means that the corresponding function
  96.     value is negated, e.g. nlt is the C expression "-(a < b)".
  97.  
  98.     maxs, mins, maxu, minu are binary (i.e. two argument) signed
  99.     respectively unsigned max and min.
  100.  
  101.     sgn is the unary sign function; -1 for negative, 0 for zero, and +1
  102.     for positive arguments.
  103.  
  104.     abs and nabs are absolute value and negative absolute value,
  105.     respectively.
  106.  
  107.     For a complete list of goal function and their definitions, look in
  108.     the file goal.def.  You can easily add your own goal function to
  109.     that file.
  110.  
  111.  
  112.         READING SUPEROPTIMIZER OUTPUT
  113.  
  114. The superoptimizer by default outputs sequences in high-level language like
  115. syntax.  For example, this is the output for M88000/abs:
  116.  
  117. 1:    r1:=arith_shift_right(r0,0x1f)
  118.     r2:=add_co(r1,r0)
  119.     r3:=xor(r2,r1)
  120. 2:    r1:=arith_shift_right(r0,0x1f)
  121.     r2:=add(r1,r0)
  122.     r3:=xor(r2,r1)
  123. 3:    r1:=arith_shift_right(r0,0x1f)
  124.     r2:=xor(r1,r0)
  125.     r3:=adc_co(r2,r1)
  126.  
  127. r1:=arith_shift_right(r0,0x1f) means "shift r0 right 31 steps
  128. arithmetically and put the result in r1".  add_co is "add and set carry".
  129. adc_co is the subtraction instruction found on most RISCs, i.e. "add with
  130. complement and set carry".  This may seem dumb, but there is an important
  131. difference in the way carry is set after an addition-with-complement and a
  132. subtraction.  The suffixes "_ci" and "_cio" means respectively that carry
  133. is input but not affected, and that carry is both input and generated.
  134.  
  135. The interesting value is always the value computed by the last instruction.
  136.  
  137.  
  138.         *********************************
  139.  
  140. Please send comments, improvements and new ports to tege@gnu.ai.mit.edu.
  141.  
  142. This superoptimizer was written by Torbjorn Granlund of SICS.  Tom Wood of
  143. DG made several improvements, like the clean way to describe goal functions
  144. and internal instructions.  The original superoptimizer idea is due to
  145. Henry Massalin.
  146.  
  147. Local Variables:
  148. mode: text
  149. fill-column: 75
  150. version-control: never
  151. End:
  152.